关于微信公众号

首发于安全客

前言

芜湖，这次祥云杯又是神仙打架，密码学一共有四道题，个人觉得最后一道题目有意思一些。

Random_RSA

task.py

from Crypto.Util.number import *
import gmpy2
import libnum
import random
import binascii
import os

flag=r'flag{}'

p=getPrime(512)
q=getPrime(512)
e=0x10001
n=p*q
ct=pow(flag,e,n)
print("n="+ n)
print("ct="+ ct)

dp=r''
seeds = []
for i in range(0,len(dp)):
    seeds.append(random.randint(0,10000))

res = [] 
for i in range(0, len(dp)):
    random.seed(seeds[i])
    rands = []
    for j in range(0,4):
        rands.append(random.randint(0,255))

    res.append(ord(dp[i]) ^ rands[i%4])
    del rands[i%4]
    print(str(rands))

print(res) 
print(seeds)

题目不长，也意外的简单，值得一提的是题目介绍：一把梭，好像不行哦。

然而好像就是一把梭的题目吖，没get到出题人的点喔，而且很奇怪的是，题目用的python2的环境，却直接在给flag字符串做整型pow操作，属实奇怪。

回到题目本身，倒也没有什么好说的，给了seeds，我们利用每个seeds生成四个随机数，用第四个随机数异或res的输出，然后ord一下，就能得到dp的一个数字，最后拼起来就能获得dp了。至于已知e,n,dp三个参数解密c获得明文，这里就不再赘述了，一把梭的事。

from Crypto.Util.number import *
import gmpy2

import random
import binascii
import os


seeds=[...]
dps=[]
res = [...]

for i in range(0, len(res)):
    random.seed(seeds[i])
    rands = []
    for j in range(0,4):
        rands.append(random.randint(0,255))
    dps.append(res[i]^rands[i%4])


dp = int(''.join(chr(i) for i in dps))
n=...
ct=...
e=0x10001

def rsa_nedp(n,e,dp):
	for i in range(1,e):
		if (dp*e-1)%i == 0:
			if n%(((dp*e-1)/i)+1)==0:
				p=((dp*e-1)/i)+1
				q=n/(((dp*e-1)/i))+1
				return p,q

p,q = rsa_nedp(n,e,dp)
d = inverse(e,p-1)
print(long_to_bytes(pow(ct,d,p)))

最后这里解密flag直接用p了，（单纯懒，少写一个字符是一个字符了）

Guess

from Crypto.Util.number import (
    bytes_to_long,
    getPrime,
    long_to_bytes,
    getRandomNBitInteger,
)
import random
import hashlib
from math import gcd
import socketserver


KEYSIZE = 512
WELCOME = "welcome to my funny challenge !!! Can you guess right 32 times in a row? "
String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"

def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q


def invert(a,p):
    x, y, q = exgcd(a,p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p

def lcm(a,b):
    return a*b // gcd(a,b)

def proof_of_work():
    STR = "".join([String[random.randint(0, len(String) - 1)] for _ in range(16)])
    HASH = hashlib.sha256(STR.encode()).hexdigest()
    return STR[:4], STR[4:], HASH


def keygen():
    # part 1
    p, q = getPrime(KEYSIZE), getPrime(KEYSIZE)
    n = p * q
    g = n + 1
    LAMBDA = lcm(p - 1, q - 1)

    # part 2
    _key = open("key", "r").read()
    key = []
    for i in _key.split("\n"):
        for j in i[1:-1].split(" "):
            if int(j) not in key:
                key.append(int(j))
    assert len(key) == 80
    #assert key[0] == 119 and key[1] ==  241 and key[2] ==  718 and key[3] == 647
    return n, g, LAMBDA, key


def enc(n, g, m):
    while 1:
        r = random.randint(2, n - 1)
        if gcd(r, n) == 1:
            break
    c = (pow(g, m, n ** 2) * pow(r, n, n ** 2)) % (n ** 2)
    return c


def dec(n, g, LAMBDA, c):
    L1 = (pow(c, LAMBDA, n ** 2) - 1) // n
    L2 = (pow(g, LAMBDA, n ** 2) - 1) // n
    m = (invert(L2, n) * L1) % n
    return m


class server(socketserver.BaseRequestHandler):
    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg, bytes):
            msg += b"\n"
        else:
            msg += "\n"
            msg = msg.encode()
        self.request.sendall(msg)

    def handle(self):
        # print("Service start.")
        # START, END, HASH = proof_of_work()
        # self._send("SHA-256(?+{}) == {}".format(END, HASH))
        # RCV = self._recv().decode()
        # if RCV != START:
        #     return
        # flag = open("flag", "rb").read()
        # self._send(WELCOME)
        # step 1. keygen
        for _ in range(32):
            self._send("round " + str(_+1))
            n, g, LAM, KEY = keygen()
            self._send("Step 1 - KeyGen. This is my public key.")
            self._send("n = " + str(n))
            self._send("g = " + str(g))
            # step 2. Phase 1
            self._send(
                "Step 2 - Phase 1. Now, you can give me one ciphertexts,I will return the corresponding plaintext."
            )

            self._send("Please give me one decimal ciphertext.")
            cipher = int(self._recv().decode())
            print(cipher)
            plaintext = str(dec(n, g, LAM, cipher))
            self._send("This is the corresponding plaintext.")
            self._send(plaintext)

            # step 3. challenge
            self._send(
                "Step 3 - Challenge. Now, you must give me two decimal plaintexts(m0,m1), I will encry them and return a ciphertext randomly"
            )
            self._send("Give me m0.")
            plaintext1 = int(self._recv().decode())
            self._send("Give me m1.")
            plaintext2 = int(self._recv().decode())

            if (
                plaintext1 <= 2
                or plaintext2 <= 2
                or len(bin(plaintext1)) != len(bin(plaintext2))
            ):
                return
            R = 2 * random.randint(0, 39)
            I = random.randint(0, 1)
            cipher1 = enc(n, g, plaintext1 * plaintext2 * KEY[R])
            cipher2 = enc(n, g, plaintext1 * plaintext2 * KEY[R + 1])
            self._send("This is a ciphertext.")
            self._send(str([cipher1, cipher2][I]))

            # step 4. Phase 2

            self._send(
                "Step 4 - Phase 2. Now, you can give me some ciphertexts,I will return the corresponding plaintext.But you can not give me the ciphertext that I give you in step 3."
            )
            self._send("Please give me one decimal ciphertext ")
            cipher = int(self._recv().decode())
            plaintext = str(dec(n, g, LAM, cipher))
            if int(plaintext) == plaintext1 * plaintext2 * KEY[R] or int(plaintext) == plaintext1 * plaintext2 * KEY[R+1]:
                print(plaintext)
                return
            self._send("This is the corresponding plaintext.")
            self._send(plaintext)

            # step.5 Guess
            self._send(
                "Step 5 - Guess. You must tell me which ciphertext was I give you in step 3, 0 or 1(m0 -> c0 , m1 -> c1)?"
            )
            Guess = int(self._recv().decode())

            if Guess == I:
                self._send("Good! You are right")
            else:
                self._send("Sorry!")
                return
        self._send(flag)

class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = "0.0.0.0", 10001
    server = ForkedServer((HOST, PORT), server)
    server.allow_reuse_address = True
    server.serve_forever()

这道题代码还挺长的，不过并不难看懂。

首先再定义server类上面的是enc和dec，其实就是paillier系统，不熟悉的读者可以移步我的这一片文章。

然后这道题目不知道是不是非预期了，因为题目给的hint我并没有到。step2的交互我也没有利用。（太奇怪了，预期该是啥样呢）

由于题目用的pailliar密码系统，具有同态（竟然说不上是乘法同态还是加法同态，只能说两个明文之和的密文，是两个明文分别的密文之积）

我们看到step4-5

题目向我们要两个明文plaintext1和plaintext2，然后加密的内容为

cipher1 = enc(n, g, plaintext1 * plaintext2 * KEY[R])
cipher2 = enc(n, g, plaintext1 * plaintext2 * KEY[R + 1])

由于plaintext1和plaintext2可控，而两条密文的唯一区别是KEY的内容不一样。然后题目加密后随机返回一条，让我们猜返回的是哪个。

我们可以看到，这加密的明文唯一的区别就是用的是KEY[R]和KEY[R+1]，而R = 2 * random.randint(0, 39)，是一个偶数。

那么这里我们选择“炼丹”：

首先我们可以利用同态获取到实际的KEY：题目在step3发送密文cipher后，在step4会帮我们解密一条数据，但是这条数据不能是服务器加密的那两条密文之一，那么，我们就给他cipher * enc(5)，这样他就会解密后并返回plaintext1 * plaintext2 * KEY[R] + 5 或者 plaintext1 * plaintext2 * KEY[R+1] + 5, 我们再处理一下（不处理问题也不大），减掉5，除掉plaintext1 * plaintext2，就可以获取一个KEY_i 了。

然后我们到step5，我们只知道了一个KEY_i，但是不知道它具体的位置，我们直接发送0，如果返回正确，那么我们知道，这个KEY_i 在偶数位，如果返回错误，服务断掉，那么我们知道，这个KEY_i 在奇数位。那么，由于服务端的KEY序列是固定的，那么我们就开始炼丹咯。

我们构造两个数组，一个存奇数位，一个存偶数位。每次连上去，我们解密得到一个KEY_i，如果这个KEY_i 在我们的数组里，我们就能够直接返回正确答案，如果不在，我们就”炼“，猜对了，放进数组，继续猜，猜错了，放进数组，重新连。（再非不过80次连接）

from Crypto.Util.number import (
    bytes_to_long,
    getPrime,
    long_to_bytes,
    getRandomNBitInteger,
)
import random
import hashlib

KEYSIZE = 512
WELCOME = "welcome to my funny challenge !!! Can you guess right 32 times in a row? "
String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"
from math import gcd
def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q


def invert(a,p):
    x, y, q = exgcd(a,p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p

def lcm(a,b):
    return a*b // gcd(a,b)

def proof_of_work():
    STR = "".join([String[random.randint(0, len(String) - 1)] for _ in range(16)])
    HASH = hashlib.sha256(STR.encode()).hexdigest()
    return STR[:4], STR[4:], HASH



def enc(n, g, m):
    while 1:
        r = random.randint(2, n - 1)
        if gcd(r, n) == 1:
            break
    c = (pow(g, m, n ** 2) * pow(r, n, n ** 2)) % (n ** 2)
    return c


def dec(n, g, LAMBDA, c):
    L1 = (pow(c, LAMBDA, n ** 2) - 1) // n
    L2 = (pow(g, LAMBDA, n ** 2) - 1) // n
    m = (invert(L2, n) * L1) % n
    return m

from pwn import *
from pwnlib.util.iters import mbruteforce
from hashlib import sha256

#context.log_level = 'debug'

def proof_of_work(sh):
    sh.recvuntil("?+")
    suffix = sh.recvuntil(')').decode("utf8")[:-1]
    log.success(suffix)
    sh.recvuntil("== ")
    cipher = sh.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==  cipher, string.ascii_letters + string.digits, length=4, method='fixed')
    sh.sendline(proof)
vanish=[]

#奇
s=[]
#偶
ss=[]


for _ in range(80):
	sh=remote("47.104.85.225","57811")
	proof_of_work(sh)

	while True:
		tmp = sh.recvuntil("n = ")
		n = int(sh.recvuntil("\n")[:-1])
		sh.recvuntil("g = ")
		g = int(sh.recvuntil("\n")[:-1])
		sh.recvuntil("decimal ciphertext.\n")
		sh.sendline("123")
		sh.recvuntil("Give me m0.\n")
		sh.sendline("5")
		sh.recvuntil("Give me m1.\n")
		sh.sendline("5")
		sh.recvuntil("This is a ciphertext.\n")
		c = int(sh.recvuntil("\n")[:-1])
		sh.recvuntil("Please give me one decimal ciphertext \n")
		sh.sendline(str((enc(n,g,5)*c)%(n**2)))
		sh.recvuntil("This is the corresponding plaintext.\n")
		m = (int((sh.recvuntil("\n")[:-1]))-5)//25
		sh.recvuntil("0 or 1(m0 -> c0 , m1 -> c1)?\n")
		if m in s:
			sh.sendline('1')
			tmp = sh.recvuntil("\n")
		elif m in ss:
			sh.sendline('0')
			tmp = sh.recvuntil("\n")
		else:
			sh.sendline('1')
			tmp = sh.recvuntil("\n")
			if b"Good! You are right" in tmp:
				s.append(m)
			elif b"Sorry" in tmp:
				ss.append(m)
				sh.close()
				break
		print(s)
		print(ss)

myRSA

# myRSA
from Crypto.Util.number import getPrime,bytes_to_long as b2l
from math import gcd
import hashlib
import random
import socketserver


KEYSIZE = 512
alpha = 2.0314159265358979
WELCOME = 'Welcome to use my better RSA!!!!!!So, what do you want now?'
menu = '1. encry \n2. getflag\n3. exit'
String = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz'

def proof_of_work():
    STR = ''.join([String[random.randint(0,len(String)-1)] for _ in range(16) ])
    HASH = hashlib.sha256(STR.encode()).hexdigest()
    return STR[:4],STR[4:],HASH

def key_gen():
    while True:
        p,q = getPrime(KEYSIZE),getPrime(KEYSIZE)
        e = 0x10001
        if gcd(e,(p-1)*(q-1)):
            break
    key = [getPrime(int(KEYSIZE*alpha)) for _ in range(2)]
    return (p,q,e),key

# encrypto
def encry(message,key,p,q,e):
    k1,k2 = key[0],key[1]
    x = p**2 * (p + 3*q - 1 ) + q**2 * (q + 3*p - 1) 
    y = 2*p*q + p + q
    z = k1 + k2 
    c = pow(b2l(message),e,p*q)
    return x * c + y * c + z


# get flag
def getflag(flag,key,p,q,e):
    return encry(flag,key,p,q,e)



class server(socketserver.BaseRequestHandler):
    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg , bytes):
            msg += b'\n'
        else:
            msg += '\n'
            msg = msg.encode()
        self.request.sendall(msg)

    def handle(self):
        START,END,HASH = proof_of_work()
        self._send('SHA-256(?+{}) == {}'.format(END,HASH))
        RCV = self._recv().decode()
        if RCV != START:
            return
        self._send("I'm a CryptoRookie,so my Crypto system take time, please wait a minute XD!")
        (p,q,e),key = key_gen()
        flag  = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
        self._send(WELCOME)
        self._send('This is my public key:\nn = {}\ne = {}'.format(str(p*q),str(e)))
        for _ in range(16):
            self._send(menu)
            COI = int(self._recv().decode())
            if COI == 1 :
                self._send('Give me your message')
                message = self._recv()
                self._send('Your encry message:')
                self._send(str(encry(message,key,p,q,e)))
            elif COI == 2:
                self._send('This is your favourite:\n')
                self._send(str(encry(flag,key,p,q,e)))
            elif COI == 3:
                self._send('Bye~')
                break
class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    server = ForkedServer((HOST, PORT), server)
    server.allow_reuse_address = True
    server.serve_forever()

这道题，emmm，也是奇怪的加密方式，

def encry(message,key,p,q,e):
    k1,k2 = key[0],key[1]
    x = p**2 * (p + 3*q - 1 ) + q**2 * (q + 3*p - 1) 
    y = 2*p*q + p + q
    z = k1 + k2 
    c = pow(b2l(message),e,p*q)
    return x * c + y * c + z

题目提供提供十六次交互，它可以帮你加密，但每次加密用的z随机

x * c + y * c + z =( x+y ) * c + z

其中( x+y ) = ( p+q )^3 - ( p+q )^2 + ( p+q ) - 4 * n

那么我们发送明文 ’\x01’ 过去，就能得到enc = x + y + z，所以 enc + 4 * n = (p+q)^3 - (p+q)^2 + (p+q) + z

我们可以将其看作关于（p+q）的方程 f(x) ，由于z不知道，没法根据返回值解一个具体的值x。

但是算一下长度，(p+q)^3 有 513 * 3 = 1539 bit，z 才 1024bit左右，相对比较小。那么我们直接不管z，去解方程（这里我是用2分法去逼近的），然后我们可以得到一个大概的值。

有了大概的 $x \approx (p+q)$，再利用n，就能得到一个大概的p值，

$p \approx \frac{x - \sqrt{x^2 - 4n}}{2}$

有了大概的p值，我们可以本地起一组数据看看和真正的p值差多少，可以发现就差小几万，那么我们直接一手small_roots恢复p。p，q都恢复了，我们直接交互拿到flag的密文 ( x + y) * pow(flag, e, n) + z

直接整除 (x + y) 得到pow(flag, e, n)，（z太小了，整除就给消没了），后面，rsa解密，得到flag。

P.S.不懂出题人干嘛搞一个genkey浪费时间，有啥必要么，还是说，又又又又又又又又又又又又非预期了？确实没用到16次交互。

#交互拿到数据a = x + y + z; c = pow(flag,e,n) * (x + y) + z

from Crypto.Util.number import *

def f(x):
    return x**3 - x**2 + x + 4*n

n = ...
e = 65537

a = ...

c = ...



floor = 0
sky = 2**1041
while floor+1 < sky:
    mid = (floor + sky) // 2
    if f(mid) < a:
        floor = mid
    else:
        sky = mid

import gmpy2 

p_sub_q = gmpy2.iroot(int(mid**2-4*n),int(2))[0]
pw = (mid-p_sub_q)//2

N = n
pbar = pw
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
ff = int(pbar) + x
x0 = ff.small_roots(X=2^40, beta=0.4)[0]
p = int(int(pbar) + x0)
n = int(n)
q = n // p

tmp = f(p+q)
c //= tmp
print(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),n)))

ok，终于来到最有意思的一题了，也是足足做了我快5个小时（虽然中途思路断了的时候去把XMAN结营赛的密码学赛题AK了下）

secret_share

task

#! /usr/bin/env python
from libnum import n2s, s2n
from random import getrandbits
from hashlib import sha256
import SocketServer
from secret import flag

p, g = 0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3, \
       0x85fd9ae42b57e515b7849b232fcd9575c18131235104d451eeceb991436b646d374086ca751846fdfec1ff7d4e1b9d6812355093a8227742a30361401ccc5577


def h2(m):
    return int(sha256(m).hexdigest(), 16)


def key_gen(nbits):
    s = getrandbits(nbits) % p
    while s.bit_length() < nbits - 2:
        s = getrandbits(nbits) % p
    pk = pow(g, s, p)
    return pk, s


def enc(m, pk):
    m = s2n(m)
    e, v = getrandbits(256), getrandbits(256)
    E, V = pow(g, e, p), pow(g, v, p)
    s = v + e * h2(n2s(E) + n2s(V))
    c = m * pow(pk, e + v, p) % p
    cap = (E, V, s)
    return c, cap


def rk_gen(sk, pki, group=9):
    x, r = getrandbits(512) % p, getrandbits(512) % p
    prefix = n2s(pow(g, x * sk, p)).rjust(64, '\x00')
    encoder = [1, -pow(pki, x * sk, p) % p]
    for i in range(1, group + 1):
        pkj = getrandbits(512)
        new_encoder = [1]
        cur = pow(pkj, x * sk, p)
        for j in range(1, i + 1):
            new_encoder.append((encoder[j] + (-1) * cur * encoder[j - 1]) % p)
        new_encoder.append(encoder[i] * cur * (-1) % p)
        encoder = new_encoder
    encoder[-1] += r
    dd = h2(prefix + n2s(r).rjust(64, '\x00')) | 1
    rk = sk * dd
    return rk, encoder[1:], prefix


def re_enc(rk, cipher):
    c, (E, V, s) = cipher
    E_ = pow(E, rk, p)
    V_ = pow(V, rk, p)
    s_ = s * rk % p
    return c, (E_, V_, s_)


class ThreadedTCPServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass


class EncHandler(SocketServer.BaseRequestHandler):
    def handle(self):
        self.request.sendall("Welcome to our netdisk system! Our system store only users' ciphertext\n")
        self.request.sendall("Now you can choose what you wanna do\n")
        self.request.sendall("1. generate your key\n2. start challenge\n2. get the ciphertext")
        pk_of_one_user, sk_of_one_user = key_gen(512)
        cipher = enc(flag, pk_of_one_user)
        pk, sk = key_gen(512)
        while 1:
            mul = 1
            self.request.sendall('Input your choice\n')
            self.request.sendall("choice>")
            choice = self.request.recv(16).strip()
            if choice == '1':
                self.request.sendall('Please take good care of it!\n' + hex(pk) + ',' + hex(sk) + '\n')
            elif choice == '2':
                group_list = [32, 64, 128, 256]
                for group in group_list:
                    m = getrandbits(200)
                    plaintext = n2s(m)
                    cur_cipher = enc(plaintext, pk_of_one_user)
                    rk, encoder, prefix = rk_gen(sk_of_one_user, pk, group=group)
                    mul *= rk
                    mul %= p
                    new_cipher = re_enc(rk, cur_cipher)
                    self.request.sendall('The cipher shared to you\n' + str(new_cipher) + '\n')
                    self.request.sendall('prefix, encoder = ' + str((encoder, prefix.encode('hex'))) + '\n')
                    ans = self.request.recv(1024).strip()
                    if int(ans, 16) != m:
                        exit(1)
                self.request.sendall('You are a clever boy! Now I can share you some other information!\n' + hex(mul) + '\n')
            elif choice == '3':
                self.request.sendall(str(cipher) + '\n')
                exit(1)
            else:
                continue


if __name__ == "__main__":
    HOST, PORT = "0.0.0.0", 1213
    server = ThreadedTCPServer((HOST, PORT), EncHandler)
    server.serve_forever()

还好，也就百来行，代码量不大，

我们以目标驱使，找到获取flag的地方，cipher = enc(flag, pk_of_one_user)

看到这个pk_of_one_user，

def key_gen(nbits):
    s = getrandbits(nbits) % p
    while s.bit_length() < nbits - 2:
        s = getrandbits(nbits) % p
    pk = pow(g, s, p)
    return pk, s

pk_of_one_user, sk_of_one_user = key_gen(512)

基于离散对数问题的公私钥对 $pk \equiv g^{sk} \pmod p$

然乎看到enc的加密方式

def enc(m, pk):
    m = s2n(m)
    e, v = getrandbits(256), getrandbits(256)
    E, V = pow(g, e, p), pow(g, v, p)
    s = v + e * h2(n2s(E) + n2s(V))
    c = m * pow(pk, e + v, p) % p
    cap = (E, V, s)
    return c, cap

可以化为式子： $c \equiv m \cdot pk^{e+v} \equiv m \cdot g^{(e+v)\cdot sk} \equiv m \cdot (E \cdot V) ^ {sk}\pmod p $

那么想获取flag，就要搞到这个私钥sk咯，看看怎么能搞到。

第一目标：拿到sk

可以看到交互提供三个功能，第一个，获取你自己的公私钥对 pk，sk

再看下第三个，返回flag的密文，

然后第二个比较长，核心功能也就在这里了，

group_list = [32, 64, 128, 256]
for group in group_list:
    m = getrandbits(200)
    plaintext = n2s(m)
    cur_cipher = enc(plaintext, pk_of_one_user)
    rk, encoder, prefix = rk_gen(sk_of_one_user, pk, group=group)
    mul *= rk
    mul %= p
    new_cipher = re_enc(rk, cur_cipher)
    self.request.sendall('The cipher shared to you\n' + str(new_cipher) + '\n')
    self.request.sendall('prefix, encoder = ' + str((encoder, prefix.encode('hex'))) + '\n')
    ans = self.request.recv(1024).strip()
    if int(ans, 16) != m:
        exit(1)

流程描述：

他会生成一个随机数m，

然后它的公钥加密m得到cur_cipher，

然后将它的私钥和我们的公钥放进rk_gen这个函数，会得到 rk, encoder, prefix

然后mul = mul * rk % p，

然后用rk，re_enc这个cur_cipher

然后把re_enc后的密文，encoder, prefix 发送给我们。

然后然我们解密m，对了继续，错了拜拜。

循环四次，都通过返回给你mul。

整理逻辑。如果我们都通过了，就能拿到 mul = rk_1 * sk * rk_2 * sk * rk_3 sk * rk_4 % p

有了这个mul，有啥意义么？这里还看不出来，我们继续往前走先，不过有一个问题很明确，既然出题人就这么布置了，我们当然是需要解密m了。

第二目标，解密m

想要解密m，我们相关信息只有re_enc后的cipher，当前轮次的encoder, prefix

看看这个re_enc

def re_enc(rk, cipher):
    c, (E, V, s) = cipher
    E_ = pow(E, rk, p)
    V_ = pow(V, rk, p)
    s_ = s * rk % p
    return c, (E_, V_, s_)

可以发现，整个函数都没有操作c，就更新了一下E, V, s

那么更新一下我们手里的信息，$cipher \equiv m \cdot g^{sk \cdot (e+v) } \equiv m \cdot (E\cdot V) ^{sk},E_ \equiv E^{rk},V_ \equiv V^{rk}, s \equiv s \cdot rk $

就这么多了，我们再去看看返回encoder, prefix 的 rk_gen函数，

def rk_gen(sk, pki, group=9):
    x, r = getrandbits(512) % p, getrandbits(512) % p
    prefix = n2s(pow(g, x * sk, p)).rjust(64, '\x00')
    encoder = [1, -pow(pki, x * sk, p) % p]
    for i in range(1, group + 1):
        pkj = getrandbits(512)
        new_encoder = [1]
        cur = pow(pkj, x * sk, p)
        for j in range(1, i + 1):
            new_encoder.append((encoder[j] + (-1) * cur * encoder[j - 1]) % p)
        new_encoder.append(encoder[i] * cur * (-1) % p)
        encoder = new_encoder
    encoder[-1] += r
    dd = h2(prefix + n2s(r).rjust(64, '\x00')) | 1
    rk = sk * dd
    return rk, encoder[1:], prefix

先不管其他的，看到最下面，rk = sk * dd

我们回想到 mul = rk_1 * sk * rk_2 * sk * rk_3 sk * rk_4 % p ，

那么可以转化为 mul = sk^4 * dd1 * dd2 * dd3 * dd4 % p ，

有了dd的product，那么我们再在模p下给sk^4开个四次根就能拿到sk了！

而 dd = h2(prefix + n2s(r).rjust(64, ‘\x00’)) | 1，其中prefix已知，所以目标很明确

第三目标，获取r

我们能够注意到，返回给我们的encder与r相关， 其中encoder[-1] += r，所以我们需要恢复出原来的encoder，

那就得从头看这个函数了，我们首先看到，prefix = n2s(pow(g, x * sk, p)).rjust(64, ‘\x00’)，其中x是未知随机数，sk是服务端公钥，

然后初始 encoder = [1, -pow(pki, x * sk, p) % p]，划重点，需要注意到，这里的pki，用的是再step1中给我们的pk，我们是知道其对应的sk的！我们把自己的sk记为ski，避免搞混，那么式子：$encoder \equiv - pki^{x \cdot sk} \equiv -g^{ski \cdot s \cdot sk}$，这个时候，再去看看prefix的表达式 $prefix = g^{s \cdot sk}$，就只差一个 ski ，而这个ski我们是已知的，所以我们就获得了初始 encoder = [1, -pow(prefix, ski, p) % p]

核心的迭代来了

for i in range(1, group + 1):
    pkj = getrandbits(512)
    new_encoder = [1]
    cur = pow(pkj, x * sk, p)
    for j in range(1, i + 1):
        new_encoder.append((encoder[j] + (-1) * cur * encoder[j - 1]) % p)
    new_encoder.append(encoder[i] * cur * (-1) % p)
    encoder = new_encoder

cur = pow(pkj, x * sk, p)，pkj是一个随机数，所以cur显然无法直接得到，然后是循环里的 new_encoder.append((encoder[j] + (-1) * cur * encoder[j - 1]) % p)

走出后还来一下 new_encoder.append(encoder[i] * cur * (-1) % p)

这里建议画个美丽的图会稍微清晰一些

可以看到，如果对于cur2那一行，在我们知道 x 的前提下，我们是能够通过第二项获取到 （cur1 + cur2） 的值的，

在我们知道（cur1 + cur2） 的值的前提下，我们是能够获得第三项中 （cur1 * cur2）的值的。

有了（cur1 * cur2）的值，我们再将他乘以x，我们就获得了encoder最后一项的值了。

芜湖，起飞！（如果觉得就分析这么三轮还不够的化，可以再画第四轮，就很清晰了）

那么我们迎来了处理 encoder的核心解法，基本上可以宣布此题告破了。

我们只需要用题目给的 encoder 和 prefix，进行上述操作

encoder,prefix = ...

x = -pow(prefix,sk,p)%p
encoder_i=1
for i in encoder[:-1]:
    encoder_i = (i-encoder_i*x)%p
r = (encoder[-1] - encoder_i*x)%p

就能够获取到r了！

有了r，我们就可以生成dd，但是为了获取到最后的mul，我们还要去解密一下m，

再此看到m的密文 $cipher \equiv m \cdot g^{sk \cdot (e+v) } \equiv m \cdot (E\cdot V) ^{sk}$

我们还知道 $rk = sk \cdot dd,E_ \equiv E^{rk},V_ \equiv V^{rk}, s \equiv s \cdot rk $

解密m就要知道 $(E\cdot V) ^{sk}$

但是想要知道$(E\cdot V) ^{sk}$，就一定需要知道sk么？我们拥有$E_ \cdot V_ = (E\cdot V) ^ {rk} \equiv (E\cdot V) ^ {sk \cdot dd} $

而我们知道 dd，所以直接求一个$(E_ \cdot V_)^{dd^{-1}} \equiv (E \cdot V) ^ {sk \cdot dd \cdot dd^{-1}} \equiv (E \cdot V) ^ {sk}$，（需要注意一下，给dd求逆的时候，模的是 p - 1，这个应该不用解释了）

好了，这样我们就能解密m，通过check，拿到mul，开根得到备选sk（四次根，不出意外有多解），再用通过功能3，拿一份flag的cipher，用备选sk计算 $(E \cdot V) ^ {sk}$，求逆然后乘以cipher，然后顺利拿到flag，完结撒花！

from pwn import * 

from random import getrandbits
from hashlib import sha256
from Crypto.Util.number import *

def n2s(n):
    return long_to_bytes(n)

def s2n(n):
    return bytes_to_long(n)

def h2(m):
    return int(sha256(m).hexdigest(), 16)


def key_gen(nbits):
    s = getrandbits(nbits) % p
    while s.bit_length() < nbits - 2:
        s = getrandbits(nbits) % p
    pk = pow(g, s, p)
    return pk, s


def enc(m, pk):
    m = s2n(m)
    e, v = getrandbits(256), getrandbits(256)
    E, V = pow(g, e, p), pow(g, v, p)
    s = v + e * h2(n2s(E) + n2s(V))
    c = m * pow(pk, e + v, p) % p
    cap = (E, V, s)
    return c, cap


p, g = ...

#context.log_level = 'debug'
sh = remote("47.104.85.225","62351")
#sh = remote("0.0.0.0","1213")
sh.recvuntil("choice>")
sh.sendline("1")
sh.recvuntil("Please take good care of it!\n")
tmp = sh.recvuntil("\n")[:-1]
#获取自己的pk和sk
pk,sk = eval(tmp)
B=[]
sh.recvuntil("choice>")
sh.sendline("2")
for _ in range(4):
	sh.recvuntil("The cipher shared to you\n")
	tmp = sh.recvuntil("\n")[:-1]
	
	#获取到 re_enc(m) 后给的 c, (E_, V_, s_)
	c, (E_, V_, s_) = eval(tmp)
	sh.recvuntil("prefix, encoder = ")
	tmp = sh.recvuntil("\n")[:-1]
	
	#利用 encoder,prefix 获取r，从而得到dd
	encoder,prefix = eval(tmp)
	prefixx = prefix.decode('hex')
	prefix = int(prefix,16)
	x = -pow(prefix,sk,p)%p
	tmp=1
	for i in encoder[:-1]:
		tmp = (i-tmp*x)%p
	r = (encoder[-1] - tmp*x)%p
	prefix = n2s(pow(g, x * sk, p)).rjust(64, '\x00')
	dd = h2(prefixx + n2s(r).rjust(64, '\x00')) | 1
	B.append(dd)
	dd_ = inverse(dd,p-1)
	
	#有了dd利用 E_ * V_ 解密m
    m = inverse(pow(E_*V_,dd_,p),p)*c % p
	sh.sendline(hex(m)[2:])

sh.recvuntil("You are a clever boy! Now I can share you some other information!\n")
tmp = sh.recvuntil("\n")[:-1]

#拿着通关后给的mul，待会去开根
mul = eval(tmp)

sh.recvuntil("choice>")
sh.sendline("3")
tmp = sh.recvuntil("\n")[:-1]

#获取flag密文相关的参数
c, (E, V, s) = eval(tmp)

#把mul里的dd去掉，得到sk^4
for i in B:
	mul = mul * inverse(i,p) % p
sk_4 = mul 

sh.interactive()

拿到 sk^4 后要开根，这里我切到sagemath去直接用nth_root了

a,b = Mod(sk_4,p).nth_root(4,all=True)

tmp = pow(int(E*V),int(a),int(p))
m = c * inverse_mod(int(tmp),int(p)) % int(p)
print(long_to_bytes(m))

tmp = pow(int(E*V),int(b),int(p))
m = c * inverse_mod(int(tmp),int(p)) % int(p)
print(long_to_bytes(m))

b'flag{504d0411-6707-469b-be31-9868200aca95}'
b'\x9at\x03O\xbd;.\xb5\x97Tz$t2V\x9b\x92\xa8\x0c.O\x89V\x05\xbf\xb9\x0e\xfb\xfcRC\x8e\x948qB\xee\x92y\x02\xbf|\xf6Sq\x81\xdf;!\xd1\x9fmJ\xfb\x87#\xbb10\xa4t\xfd\xd4\x9a'

结语

整体来看，这次比赛的题目难度中等叭，第一题一把梭没啥好说的，第二题非预期的炼丹，也还行吧，赛后也没问着hint怎么用，不过第一次交互好像是用来获取lamda的，我直接用同态过check好像也是非预期了。第三题化二元方程为一元，然后二分（哦，求一下导可以知道后面是递增的所以能二分）去求一个大概解，也挺有意思的。不过最喜欢的还是最后一题，初看觉得整个代码的处理流程很冗长，但是一点点去将题目解析，将问题一点点规约下去，这种一点点拨开云雾见天日，守得云开见月明的感觉属实不错，而且难度也刚好在我的level，舒服了。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com